package leetcode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 接雨水
 */
public class PickUpRain {
    public static void main(String[] args) {
        int[] height = new int[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
//        int[] height = new int[] {4, 2, 0, 3, 2, 5};
        System.out.println(trap4(height));
    }

    /**
     * 暴力搜索法
     * @param height
     * @return
     */
    public static int trap1(int[] height) {
        int ans = 0;
        int leftMax, rightMax;
        leftMax = rightMax = height[0];
        for (int i = 0; i < height.length; i++) {
            for (int j = i; j >= 0; j--) {
                if (height[j] > leftMax) {
                    leftMax = height[j];
                    break;
                }
            }
            for (int j = i; j < height.length; j++) {
                if (height[j] >= rightMax) { // 要取大于等于
                    rightMax = height[j];
                    break;
                }
                if (j == height.length - 1) {
                    // 未找到较大值
                    rightMax = height[i];
                }
            }
            ans += Math.min(leftMax, rightMax) - height[i];
        }
        return ans;
    }

    /**
     * 动态规划双数组法
     * @param height
     * @return
     */
    public static int trap2(int[] height) {
        int len = height.length;
        int[] leftMax = new int[len];
        int[] rightMax = new int[len];
        leftMax[0] = height[0];
        rightMax[len - 1] = height[len - 1];
        for (int i = 1; i < len; i++) {
            if (height[i] > leftMax[i - 1]) {
                leftMax[i] = height[i];
            } else {
                leftMax[i] = leftMax[i - 1];
            }
        }
        for (int i = len - 2; i >= 0; i--) {
            if (height[i] > rightMax[i + 1]) {
                rightMax[i] = height[i];
            } else {
                rightMax[i] = rightMax[i + 1];
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }

    /**
     * 双指针，优化动态规划，使用两数代替数组，两数不断实现覆盖
     * @param height
     * @return
     */
    public static int trap3(int[] height) {
        int leftMax, rightMax;
        leftMax = rightMax = 0;
        // 使用双指针遍历数组
        int left, right;
        left = 0;
        right = height.length - 1;
        int ans = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) {
                ans += leftMax - height[left];
                left ++;
            } else {
                ans += rightMax - height[right];
                right --;
            }
        }
        return ans;
    }

    /**
     * 单调栈
     * @param height
     * @return
     */
    public static int trap4(int[] height) {
        Deque<Integer> deque = new ArrayDeque<>(); // 存储元素下标，其对应元素递减
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            // 说明栈顶对应的元素有区域存储雨水
            while (!deque.isEmpty() && height[deque.peek()] < height[i]) {
                int top = deque.pop();
                if (deque.isEmpty()) {
                    break;
                }
                int left = deque.peek();
                int w = i - left - 1; // 区域宽度
                int h = Math.min(height[left], height[i]) - height[top];
                ans += w * h;
            }
            deque.push(i);
        }
        return ans;
    }
}
